package cn.edu.njust.alg;

public class LIS {

	// 最长上升子序列
	public static int lis(int[] array) {
		int[] res = new int[array.length];
		res[0] = 1;
		int max = 0;
		int t = 0;
		for (int i = 1; i < array.length; i++) {
			max = Integer.MIN_VALUE;
			for (int j = 0; j < i; j++) {
				if (array[i] >= array[j]) {
					t = res[j] + 1;
				}
				if (max < t) {
					max = t;
				}
			}
			res[i] = max;
		}

		return res[array.length - 1];
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = { 1, 6, 2, 5, 4, 7 };
		System.out.println(lis(array));
	}

}
